package io.adrainty.algorithm.leetcode.lcr;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * LCR 007. 三数之和
 * @link <a href="https://leetcode.cn/problems/1fGaJU/">...</a>
 * @author AdRainty
 * @version V1.0.0
 * @since 2024/9/1 下午5:03
 */
public class LCR007 {

    private final List<List<Integer>> result = new LinkedList<>();

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length >= 3) {
            Arrays.sort(nums);
            int i = 0;
            while (i < nums.length - 2) {
                twoSum(nums, -nums[i], i);
                int tmp = nums[i];
                while (i < nums.length && nums[i] == tmp) i++;
            }
        }
        return result;
    }

    public void twoSum(int[] numbers, int target, int i) {
        int left = i + 1;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                result.add(List.of(-target, numbers[left], numbers[right]));
                int tmp = numbers[left];
                while (left < right && numbers[left] == tmp) left++;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

}
